A common set of problems normally solved with the aid of an electronic digital computer are those in which measurements of a complex physical system are used to derive or estimate other values that cannot be measured directly. For example, in an electrical transmission and distribution network with known topology and electrical characteristics, the amount of power delivered to the network by some of the generating stations and certain of the line flows may be measured. From these measurements of generator power and line flows, the voltages on the network at the various sites may be derived or estimated. This in turn permits the estimation of almost any other quantity of interest, such as other unmetered flows and voltages. Measuring every flow and voltage is not practical and/or reliable.
Problems such as these may be expressed in the following matrix form EQU Ax=z (1)
Where z is a set of measured values, such as power input from generators or line flows, x is a set of unknowns, such as voltages, and A is a matrix of coefficients, based for example on the network topology and electrical characteristics, and relating the currents z to the voltages x.
Equation (1) provides a set of simultaneous equations which may be solved for values of x. Typically, the number of measured values, and hence equations, will be greater than the number of unknown values. Thus some of the measurements are redundant. Further, to the extent that the measurements are inaccurate or the physical system is not well characterized, the equations will conflict with each other. Thus, the values x will be a best fit to inconsistent measurements.
The matrix equation (1) requires that the relationships between the measured values and the unknown values be linear, however in those situations where linear relationships are not present, the equation (1) may often be used by approximating the relationship with linear equations.
A number of computerized techniques are known for estimating or optimizing values of x based on values of z and A. In one method known as "orthogonal factorization", a set of orthogonal matrices Q.sub.1 . . . Q.sub.n are selected that produce the matrix A when multiplied by an upper triangular matrix R, that is: EQU Q.sub..tau. . . . Q.sub.3,Q.sub.2,Q.sub.1 R=A (2)
or EQU QR=A (2')
where Q.sub..tau. . . . Q.sub.3,Q.sub.2,Q.sub.1 =Q (2') PA1 where the information from matrix A has been concentrated into the upper diagonal half of the matrix R. R may be used to solve for the values of x by back substitution. From equations (1) and (2'): EQU QRx=z (7) EQU Rx=Q'z (8) PA1 where Q' is the transposition of Q which for orthogonal matrixes is equal to the inverse of Q. In this case: ##EQU5## PA1 x.sub.1 =1.2 PA1 x.sub.2 =-0.8 PA1 x.sub.3 =1.2 PA1 x.sub.4 =-0.8
The orthogonal matrices Q.sub.1 through Q.sub..tau., when factored from A, concentrate the data of matrix A into the upper right hand side of the matrix as an upper triangular matrix R. In some cases, the product of those Q matrices can be combined into a single orthogonal matrix Q. An upper triangular matrix is a matrix where all non-zero coefficients are on or above the diagonal from the northwest corner of the matrix to the southeast corner of the matrix. The upper triangular matrix R can be readily solved for values of x using the technique of back substitution as will be described below and as is well known in the art.
Thus, for example, a simple physical system may have unknown variables x.sub.1 through x.sub.4, and measured variables z.sub.1 through z.sub.5, having values of 1, -1, 1, -1, and 1, respectively. The properties of the physical system may be described by coefficients (in this case values of one or zero) in a matrix A of four columns and five rows as shown in equation (3) below. ##EQU1##
For clarity, coefficients of zero in matrix A are omitted.
Following the normal rules for matrix multiplication, equation (3) represents the following simultaneous linear equations: ##EQU2##
Note that these equations are conflicting in that the values of x.sub.1 through x.sub.4 provided in the first four equations (4a)-(4d), if summed, do not equal the value of the fifth equation.
To solve the equations (4a)-(4e) for values of x (in this case, values of x that are in "least squares" best agreement with the conflicting equations (4a)-(4e)), the matrix A may be factored by a matrix Q as follows: ##EQU3##
Where Q is determined by techniques well known in the art and described generally in Philip E. Gill et al., The Orthogonal Factorization of a Large Sparse Matrix, in "Sparse Matrix Computations", edited by J. R. Bunch et al., Academic Press (1976), hereby incorporated by reference. This orthogonal factorization produces an upper triangular matrix R as follows: ##EQU4##
Following the rules of matrix multiplication, the lower most row of matrix R provides the expression 1.1180x.sub.4 =0.8944. Thus x.sub.4 may be readily solved and substituted into an equation produced by the next to the last row of matrix R and so forth for all the equations represented by expression (10).
In this example, the following values of x.sub.1 through x.sub.4 are produced:
Note that these values differ from those indicated by equations (4a)-(4d) because they are a least squares approximation satisfying all of equations (4a)-(4e).
The process of solving for the values of x.sub.1 -x.sub.4 by back substitution of the matrix R requires ten multiplications because there are ten non-zero coefficients in R. In some current electronic computers, multiplications are a time consuming operation especially if high precision is required. Accordingly it is desirable to reduce the number of multiplication operations necessary to solve these types of problems.